The present invention relates to the field of computer graphics. More specifically, the present invention provides for efficient rendering of thick line primitives in a graphics system.
Rendering is the process of converting a description of a graphics object from a mathematical object description to a raster description usable to control a raster device.
A raster device is a device which displays images by displaying a rectangular array of uniformly spaced picture elements, or pixels, where a pixel is the smallest element of the raster device which can be addressed independently. Each pixel in the raster device's output can be made to take on a color selectable from the raster device's palette, where the palette defines a list of available colors. For many raster devices, the spacing of pixels and the palette might be fixed for a given image, but is changeable from image to image. A raster device can display an image of virtually any two-dimensional pattern, such as a line, a circle or a photograph, by appropriately coloring a set of pixels to suggest to a viewer the desired pattern. This flexibility has made raster devices the preferred visual output medium in computers and consumer products. Examples of raster devices include facsimile machines, video game displays, laser printers and computer monitors.
Rendering a shape is the process of converting a mathematical description of a shape to a collection of pixels (more precisely, pixel values) which approximate the shape. Rendering maps the coordinates of the mathematical description to the space of the pixels' coordinates and selecting those pixels that fall completely inside the shape or sufficiently so to merit inclusion in the raster representation. Rendering is expensive computationally and performed frequently so efficient methods of rendering common shapes are desirable.
In many applications, the mathematical descriptions of objects need to be rendered to pixel descriptions very quickly. The general solution to rendering is to describe the objects to be rendered in terms of their coordinates in a coordinate plane (or a coordinate space for three-dimensional images), map the pixel array to that same coordinate plane, and identify pixels which are closest to the edge of the object's edge. As is known in the art of rendering, actual rendering is slightly more complicated, as specific solutions may need to take into account shading, aliasing effects and other distortions caused by the quantization of mathematical descriptions of objects to fit the constraints inherent in a pixelated display.
Mathematically, a true line has no thickness. A line without thickness can be easily rendered by mapping the line to the coordinate space and identifying the pixels closest to the line in the coordinate plane. By contrast, a thick line has a finite, nonzero thickness. Of course, when rendering a line of zero width, the result is not a zero width line, but a line of a minimum thickness (usually, one pixel wide). As used herein, the term "thick" simply means that the line has a finite, nonzero thickness, to distinguish a line from a "thin" line, which refers herein to a line of zero width. When referring to the relative thickness of thick lines, the terms "heavy" and "light" are used.
One problem not easily solved in rendering systems is the quick and accurate rendering of "thick" lines, which is quite different and considerably more difficult than that of rendering thin lines. Many suitable methods for rendering thin lines are known in the art of rendering which cannot be easily adapted to generate visually accurate thick lines efficiently.
Thick lines are often needed in an image to convey information in addition to the information conveyed by the path of the line. In many graphic designs, such as maps and blueprints, the thickness of a line conveys a great deal of information, such as whether a road is paved, or whether the line represents a wall or a wire. Many other graphics systems require accurate presentation of thick lines, such as mechanical design systems and geographic information systems (GIS).
Mathematically, a thick line can be described as the set of points touched by a pen dragged along a trajectory. The pen can be defined as a region bounded by a convex closed curve (the pen's "footprint") and the pen's "contact point". The pen's contact point is generally, but not necessarily, within the footprint. The trajectory is a continuous, open curve having a starting point and an end point, the starting and ending points defining an implicit direction for the trajectory. Thus, a thick line shape to be rendered is defined as the shape swept out by dragging the contact point of the pen along the trajectory, carrying the footprint along, usually without changing the footprint's orientation. The mathematical thick lines thus described are used to model the marks made by writing instruments such as pens or pencils on paper or other writing surfaces.
FIG. 1 is a graphical view of a thick line 10, which is defined by a trajectory 12 and a "pen" having a contact point 13 and a footprint 14 (which happens to be a circular footprint). The resulting image of thick line 10 is the shape 15 bounded by borders 16. As shown, trajectory 12 has a start point 17 and a direction indicated by an arrowhead 18, and an end point 19. If thick line 10 were to be manually drawn on a sheet of paper, the drafter could do so by dragging a circular pen having footprint 14 over trajectory 12 from start point 17 to end point 19 in direction 18. Of course, the exact same line can be drawn by dragging the pen from end point 19 to start point 17. In other words, the selection of direction 18 over its opposite is arbitrary. However, when implemented using a computer which processes instructions in serial order, one of the directions needs to be specified.
FIG. 1 depicts a particular case of the general problem faced by computer graphics systems in drawing thick lines. In this particular case, the footprint is circular, the thick line is an unpatterned line (a "patterned line" might comprise a pattern of "on" and "off" segments), and the trajectory is smooth (i.e., it has no tangential discontinuities such as kinks or corners). In the more general case, footprint 14 might be replaced with a radially asymmetric convex shape such as an ellipse, an oval or any other closed convex curve or the trajectory might be more complicated.
Many computer graphics systems render a thick line described by a footprint, contact point and trajectory by the simpler process of rendering one or more regions enclosed by closed boundaries. In FIG. 2, a thick line 20 is represented by a collection of regions 21 delimited by closed boundaries 22. Two such collections 24, 26 are shown in FIG. 2. Different collections result from different operating parameters, such as the desired approximation accuracy, the efficiency with which the closed regions can be computed, the number of closed boundary elements needed to represent a given thick line and the nature of the elements used to represent the thick line (polygons or more general shapes). All such methods, however, have to contend with the basic problem of computing, either exactly or approximately, the boundaries that bound the two sides of the thick line from a description of the pen's footprint, orientation and trajectory. These boundaries are referred to as the "envolvents" of the thick line. Once the envolvents of a thick line are determined, the shading of the thick line can proceed using conventional methods used for filling bounded shapes. For an example of envolvents, refer to the boundary 16 shown in FIG. 1.
FIG. 3 illustrates the general approach to calculating envolvents. A portion of a thick line 30 is defined by a footprint 31, a trajectory 32 and a contact point 33. The result sought is the paths of the envolvents 34, 35. Envolvents 34, 35 have been assigned directions as shown by arrowheads 36 according to an arbitrary rule that the left envolvent (as viewed in the direction of travel) is given the same direction as the trajectory and the right envolvent is given the opposite direction. A person skilled in computer graphics would understand that by joining the ends of the envolvents in an appropriate manner, one can form a closed boundary (itself a trajectory) enclosing all the points that are part of thick line 30.
Thus, the problem of rendering a thick line can be reduced to two steps, one of determining the envolvents and one of rendering the shape defined by the continuous closed curve formed by the envolvents with their assigned directions and the curves used to connect their endpoints, under a nonzero winding rule.
As shown in FIG. 3, the envolvents might be more complex curves than the trajectories and footprints from which they arise. Envolvent 34, in particular, illustrates that envolvents may exhibit tangent discontinuities even when the trajectory and the footprint do not.
Where only one envolvent is to be generated, computational complexity is not an issue. However, where many envolvents must be generated quickly, such as in rendering text or rendering a map with many thick lines of varying thicknesses and trajectories, a computationally efficient method or apparatus for generating envolvents from a trajectory, footprint and contact point is needed.